In shared memory scheduling architectures, data received from ingress sources are temporarily stored in a commonly shared memory space. The stored data are then sent to egress destinations based on an egress scheduling algorithm. The amount of storage space determines system latency, the ability to handle egress congestion, and system cost. When egress traffic is congested, the shared memory will eventually become fully occupied. At that point, all ingress data will be dropped due to lack of memory space. This is known as tail drop, and distributes memory space unfairly among ingress sources.
In a system with multiple egress queues, WRED (Weighted Random Early Detection, also known as Weighted Random Early Discard) is a common way to address the above issue by monitoring the average queue size and dropping data based on statistical probabilities. If the shared memory is almost empty, all incoming data are accepted. As the amount of stored egress queue data grows and the shared memory occupancy increases, the probability for dropping incoming data also increases. When the shared storage space is full, the probability has reached 1 and all incoming data are dropped. WRED is considered fairer than tail drop in managing shared memory in that the more data an ingress source outputs to egress queues, the more likely it is that data from that source will be dropped.
However, WRED cannot take into account the storage capacity needs of an egress scheduler. WRED operates at the input of the egress queues in a shared memory scheduling architecture and would not be aware of scheduling parameters applied in scheduling data out of those queues. In addition, WRED cannot manage shared memory efficiency while maintaining an average queue size for all of the egress queues. For example, if egress transmission is so congested that the egress scheduler can only transmit data from a high precedence queue, the data in other egress queues can only be stored and will have little chance to be transmitted. The shared memory space occupied by lower precedence data, however, can never be released by WRED and other queue input data dropping mechanisms. The resulting storage space shortage can eventually cause problems such as:                1. very long latency for data from low precedence queues;        2. ingress drop of all high precedence data as well as low precedence data;        3. egress scheduling errors since not enough high precedence data are stored in the shared memory to fulfill egress bandwidth;        4. when congestion is relieved, old data could flood a destination, which would be undesirable.        